package org.lijma.demo.siteplan.core.impl;

import org.lijma.demo.siteplan.core.MatchedRoute;
import org.lijma.demo.siteplan.core.NoSuchRouteException;
import org.lijma.demo.siteplan.core.StopManager;
import org.lijma.demo.siteplan.core.StopSearcher;
import org.lijma.demo.siteplan.core.bean.StopRoute;
import org.lijma.demo.siteplan.core.bean.Stop;

import java.util.*;
import java.util.logging.Logger;

public class ManagerImpl implements StopManager,StopSearcher {

    private static Logger LOG = Logger.getLogger(ManagerImpl.class.getName());

    private Map<String,Stop> stops;

    public ManagerImpl(){
        stops = new HashMap<String,Stop>();
    };

    public void addStop(String stopName) {
        if(!stops.containsKey(stopName)) {
            Stop sr = new Stop(stopName);
            stops.put(stopName,sr);
        }
    }

    public String[] getStops() {
        return stops.keySet().toArray(new String[0]);
    }

    /**
     * save the edge and weight value based on list data structure
     * @param startStopName
     * @param endStopName
     * @param weight
     */
    public void addRoute(String startStopName, String endStopName, int weight) {
        addStop(startStopName);
        addStop(endStopName);

        Stop to = stops.get(endStopName);
        StopRoute stopRoute = new StopRoute(weight,to);

        Stop from = stops.get(startStopName);
        from.addRoute(stopRoute);
    }

    public List<StopRoute> getRoutesByStop(String stopName) {
        if(!stops.containsKey(stopName)){
            return null;
        }
        return stops.get(stopName).getStopRoutes();
    }

    /**
     * @param stopNames
     * @return
     * @throws NoSuchRouteException
     */
    public int findDistanceOfRoutes(List<String> stopNames) throws NoSuchRouteException {
        if(stopNames == null || stopNames.size() <= 1){
            throw new NoSuchRouteException();
        }

        int weight = 0;
        for(int i=0; i<stopNames.size(); i++){
            if(!stops.containsKey(stopNames.get(i))){
                throw new NoSuchRouteException();
            }

            if(i > 0){
                List<StopRoute> parentStopRoutes = stops.get(stopNames.get(i-1)).getStopRoutes();
                if(parentStopRoutes == null || parentStopRoutes.size() == 0){
                    throw new NoSuchRouteException();
                }
                boolean found = false;
                for(StopRoute stopRoute : parentStopRoutes){
                    if(stopRoute.getStop().getStopName().equals(stopNames.get(i))){
                        weight += stopRoute.getWeight();
                        found = true;
                        break;
                    }
                }
                if(!found){
                    throw new NoSuchRouteException();
                }
            }
        }
        return weight;
    }

    /**
     * if no trips found, there will be return 0 instead NO SUCH ROUTE
     * @param startStop
     * @param endStop
     * @param maximumStops
     * @return
     */
    public List<List<String>> getTripsByMaximumSteps(String startStop, String endStop, int maximumStops) {
        if(!stops.containsKey(startStop) || !stops.containsKey(endStop)){
            LOG.warning("no such trip found for : "+startStop+" to "+ endStop);
            return Collections.EMPTY_LIST;
        }

        List<List<String>> trips = new ArrayList<List<String>>();
        LinkedList currentTrip = new LinkedList<String>();
        currentTrip.add(startStop);
        searchFromStops(startStop, endStop, 1, maximumStops, trips, currentTrip);
        return trips;
    }

    /**
     * base on DFS, Depth-First-Search algorithm
     * @param start
     * @param end
     * @param level
     * @param maxLevel
     * @param trips
     * @param currentTrap
     */
    private void searchFromStops(String start, String end, int level, int maxLevel,List<List<String>> trips,LinkedList<String> currentTrap){
        if(level > maxLevel){
            return;
        }

        List<StopRoute> stopRoutes = stops.get(start).getStopRoutes();
        if(stopRoutes == null || stopRoutes.size() == 0){
            return;
        }

        for(StopRoute currentStop : stopRoutes){
            currentTrap.add(currentStop.getStop().getStopName());

            if(currentStop.getStop().getStopName().equals(end)){
                LinkedList<String> matchedTrap = new LinkedList<String>(currentTrap);
                trips.add(matchedTrap);
                currentTrap.removeLast();
                continue;
            }

            searchFromStops(currentStop.getStop().getStopName(),end,level+1,maxLevel,trips,currentTrap);
            currentTrap.removeLast();
        }
        return;
    };

    /**
     * if no trips found, there will be return 0 instead NO SUCH ROUTE
     * @param startStop
     * @param endStop
     * @param requiredStops
     * @return
     */
    public List<List<String>> getTripsByRequiredStops(String startStop, String endStop, int requiredStops) {
        if(!stops.containsKey(startStop) || !stops.containsKey(endStop)){
            LOG.warning("no such trip found for : "+startStop+" to "+ endStop);
            return Collections.EMPTY_LIST;
        }

        List<List<String>> trips = new ArrayList<List<String>>();
        LinkedList currentTrip = new LinkedList<String>();
        currentTrip.add(startStop);
        searchRequiredStopsByLevel(startStop, endStop, 1, requiredStops, trips, currentTrip);
        return trips;
    }

    /**
     * base on DFS, Depth-First-Search algorithm, use stop number(level) to stop the loop search
     * @param start
     * @param end
     * @param level
     * @param requiredStops
     * @param trips
     * @param currentTrap
     */
    private void searchRequiredStopsByLevel(String start, String end, int level, int requiredStops,List<List<String>> trips,LinkedList<String> currentTrap){
        if(level > requiredStops){
            return;
        }

        List<StopRoute> stopRoutes = stops.get(start).getStopRoutes();
        if(stopRoutes == null || stopRoutes.size() == 0){
            return;
        }

        for(StopRoute currentStop : stopRoutes){
            currentTrap.add(currentStop.getStop().getStopName());

            if(currentStop.getStop().getStopName().equals(end) && (level == requiredStops)){
                LinkedList<String> matchedTrap = new LinkedList<String>(currentTrap);
                trips.add(matchedTrap);
                currentTrap.removeLast();
                continue;
            }

            searchRequiredStopsByLevel(currentStop.getStop().getStopName(),end,level+1, requiredStops,trips,currentTrap);
            currentTrap.removeLast();
        }
        return;
    };

    /**
     * if no route match, return null;
     * @param startStop
     * @param endStop
     * @return
     */
    public MatchedRoute getShortestRouteAndDistance(String startStop, String endStop) {
        MatchedRoute matchedRoute = null;

        if(!stops.containsKey(startStop) || !stops.containsKey(endStop)){
            LOG.severe("no such trip found for : "+startStop+" to "+ endStop);
            return null;
        }

        MatchedRoute tmpShortest = new MatchedRoute();
        LinkedList currentTrip = new LinkedList<String>();
        currentTrip.add(startStop);
        searchWithShortestWeight(startStop, endStop,tmpShortest,currentTrip,0);

        return tmpShortest;
    }

    /**
     * base on DFS, Depth-First-Search algorithm, add visit attribute to avoid loop search.
     * @param start
     * @param end
     * @param tmpShortest
     * @param currentTrap
     * @param currentWeight
     */
    private void searchWithShortestWeight(String start, String end, MatchedRoute tmpShortest, LinkedList<String> currentTrap, int currentWeight){

        List<StopRoute> stopRoutes = stops.get(start).getStopRoutes();
        if(stopRoutes == null || stopRoutes.size() == 0){
            return;
        }

        for(StopRoute currentStop : stopRoutes){
            currentTrap.add(currentStop.getStop().getStopName());
            currentWeight += currentStop.getWeight();
            if(currentStop.getStop().getStopName().equals(end)){

                if(tmpShortest.getTotalWeight() > currentWeight || tmpShortest.getTotalWeight() == 0) {
                    LinkedList<String> matchedTrap = new LinkedList<String>(currentTrap);
                    tmpShortest.setRouteLine(matchedTrap);
                    tmpShortest.setTotalWeight(currentWeight);
                }

                currentTrap.removeLast();
                currentWeight -= currentStop.getWeight();
                continue;
            }

            if(currentStop.getStop().isVisited()){
                currentTrap.removeLast();
                currentWeight -= currentStop.getWeight();
                continue;
            }

            currentStop.getStop().setVisited(true);
            searchWithShortestWeight(currentStop.getStop().getStopName(),end,tmpShortest,currentTrap,currentWeight);

            currentStop.getStop().setVisited(false);
            currentTrap.removeLast();
            currentWeight -= currentStop.getWeight();
        }
        return;
    };


    /**
     * if no route match, return null;
     * @param startStop
     * @param endStop
     * @param maximumWeight
     * @return
     */
    public List<MatchedRoute> getMatchedRouteAndDistance(String startStop, String endStop, int maximumWeight) {
        MatchedRoute matchedRoute = null;

        if(!stops.containsKey(startStop) || !stops.containsKey(endStop)){
            LOG.severe("no such trip found for : "+startStop+" to "+ endStop);
            return null;
        }

        List<MatchedRoute> matchedRoutes = new ArrayList<MatchedRoute>();
        LinkedList currentTrip = new LinkedList<String>();
        currentTrip.add(startStop);
        searchUnderMaximumWeight(startStop, endStop,matchedRoutes,currentTrip,0,maximumWeight);

        return matchedRoutes;
    }

    /**
     * base on DFS, Depth-First-Search algorithm, use current weight to stop the loop search.
     * @param start
     * @param end
     * @param matchedRoutes
     * @param currentTrap
     * @param currentWeight
     * @param maximumWeight
     */
    private void searchUnderMaximumWeight(String start, String end, List<MatchedRoute> matchedRoutes,
                                          LinkedList<String> currentTrap, int currentWeight, int maximumWeight){
        if(currentWeight > maximumWeight){
            return;
        }

        List<StopRoute> stopRoutes = stops.get(start).getStopRoutes();
        if(stopRoutes == null || stopRoutes.size() == 0){
            return;
        }

        for(StopRoute currentStop : stopRoutes){
            currentTrap.add(currentStop.getStop().getStopName());
            currentWeight += currentStop.getWeight();

            if(currentStop.getStop().getStopName().equals(end) && (currentWeight < maximumWeight)){
                LinkedList<String> matchedTrap = new LinkedList<String>(currentTrap);
                MatchedRoute matchedRoute = new MatchedRoute();
                matchedRoute.setRouteLine(matchedTrap);
                matchedRoute.setTotalWeight(currentWeight);
                matchedRoutes.add(matchedRoute);
            }

            searchUnderMaximumWeight(currentStop.getStop().getStopName(),end,matchedRoutes,currentTrap,currentWeight,maximumWeight);
            currentTrap.removeLast();
            currentWeight -= currentStop.getWeight();
        }
        return;
    };
}
